package com.gitee.swsk33.algorithms.search;

import java.util.List;

/**
 * 查找工具类
 */
public class SearchUtils {

	/**
	 * 查找猫实例集合中特定id值的元素所在位置，找不到返回-1
	 *
	 * @param catList 猫实例集合
	 * @param id      特定id
	 * @return 位置
	 */
	public static int getIndex(List<Cat> catList, long id) {
		for (int i = 0; i < catList.size(); i++) {
			if (catList.get(i).getId() == id) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 折半查找猫实例集合中特定id值元素所在位置，找不到返回-1
	 *
	 * @param catList 猫实例集合
	 * @param id      特定id
	 * @return 位置
	 */
	public static int binarySearch(List<Cat> catList, long id) {
		// 初始化上下界下标（指针）
		int low = 0;
		int high = catList.size() - 1;
		int mid;
		while (low <= high) {
			mid = (low + high) / 2;
			// 若查找到元素则返回其位置
			if (catList.get(mid).getId() == id) {
				return mid;
			} else if (id > catList.get(mid).getId()) {
				// 否则，如果待查找元素的id比mid处的大，则将范围规定到后半部分
				low = mid + 1;
			} else {
				// 否则，在前半部分查找
				high = mid - 1;
			}
		}
		return -1;
	}

}